
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "mpi.h"

/* definice za kolik vypoctu se ma provest kontrola zprav */
#define CHECK_MSG_AMOUNT  100

/* max pocet dotazu na praci */
#define MAX_WORK_REQUESTS  5

/* minimalni velikost prace */
#define MIN_WORK_SIZE  100


/* definice barev peska pro ADUV */
#define WHITE 0
#define BLACK 1


/* definice TAGu vyuzivanych pro urceni typu zpravy */
#define TAG_OPTIMUM 0
#define TAG_SENDING_WORK 1
#define TAG_NEW_UPPER_BOUND 2
#define TAG_SENDING_TOKEN 3
#define TAG_COLLECTING_RESULT 4
#define TAG_WORK_REQUEST 5

void loadMatrix(char* filename);
int readNumberOfNodes(FILE* matrixFile);

int countEdges();
void countDegree();
void sortVertexesByDegree();


void printMatrix();
void printMatrix2(int** arr, int x, int y);
void printArray(int* arr, int n);
void printNeighbours();
void countStats();
void printStats();

void initializeSolutionArrays();

void initializeStack();
int* pop();
int push(int i, int depth);



long workload(int depth, int index);

void splitWork(int depth, int index);

void sendWork(int proc, int depth, int firstIndex, int lastIndex);

int* splitStack();

int* createWorkMessage(int depth, int firstIndex, int lastIndex);
int loadWorkMessage(int* msg);
int getWork();

void cleanup();
void solve();

int isSolution();
int isInSolution(int i, int j);

/*matice sousednosti*/
int** matrix;

/*pocet uzlu*/
int n;

/*pocet hran*/
int e;

/*pole stupnu uzlu*/
int* degree;


/*trivialni horni mez */
int trivialUpperBound;

/*aktualni horni mez vypoctu */
int upperBound;


/* delka nejlepsiho reseni, ktere nalezl proces ve svem podstromu */
int privateUpperBound;



/*trivialni dolni mez*/
int lowerBound;

/*pole uzlu serazenych sestupne (od nejvetsiho) stupne uzlu*/
int* vertexes;

/*pole indexovane cislem uzlu udavajici index v pozici pole vertexes - pro rychly pristup*/
int* vertex_position;

/*zasobnik - pole poli [index uzlu, hloubka uzlu]*/
int** stack;
int stack_size;
int stack_pointer;

/*pole zvolenych uzlu*/
int* solution;
int solution_size;

/*nejlepsi nalezene reseni*/
int* result;

/*potrebna prace*/
long totalWork; 
long avgWork;

/*p0 - pocet procesoru kterym se jiz rozeslala prace*/
int p_alloc;
/*maximalni velikost inicialni zpravy s praci*/
int maxLen;

/*pocet procesu*/
int p;

/*cislo procesu*/
int my_rank;

/* rovno jedne pokud dosla procesoru prace a zada o ni */
//int noWork;

/* 1 pokud nema praci a ani ji nesehnal */
//int workDone;

/* cyklicky pointer na uzel od ktereho ma zadat praci */
int workDonor;

/*pocet zadosti o praci*/
int numberRequests;


/*barva procesu (vyuziti u modifikovaneho peskoveho ADUV)*/
int my_color = WHITE;

//int hasToken;


/* pro mereni casu */
double t1;
double t2;



MPI_Status status;





/*********************************

funkce main

*********************************/

int main(int argc, char* argv[]){

  
  if(argc != 2){
    fputs("Pouzijte 1 argument - <jmeno vygenerovaneho souboru s matici sousednosti>\n", stderr);
    exit(1);
  }




  /* start up MPI */
  MPI_Init( &argc, &argv );

  /* find out process rank */
  MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

  /* find out number of processes */
  MPI_Comm_size(MPI_COMM_WORLD, &p);



  loadMatrix(argv[1]);
  
  countStats();
  
  initializeStack();

  initializeSolutionArrays();

  //inicializuj max velikost zpravy s inicialni praci
  maxLen = upperBound + n + 1;

  //defaultni darce prace je v log. kruhu jeho naslednik
  workDonor = (my_rank + 1) % p;  
  
  
  //zprava ve tvaru [ delka , n_0, n_1, n_2, ... , n_delka-1 ]    
  int resultMessage[trivialUpperBound + 1];          


  if (my_rank != 0) {

  	// prijem prvotni prace od procesu 0
  	int msg[maxLen];
  
	printf("P%d: Prijmam inicialni praci.\n", my_rank);

  	MPI_Recv(msg, maxLen, MPI_INT, 0, TAG_SENDING_WORK, MPI_COMM_WORLD, &status);
  	
  	int hasWork = loadWorkMessage(msg);
  
  	MPI_Barrier (MPI_COMM_WORLD);
  
  	solve();
  	
  	printf("P%d: skoncil jsem, cekam na peska.\n", my_rank);
  
    int token;
    int flag = 0;
    
    while(1){
      MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);
      
      if(flag){
      
          if(status.MPI_TAG == TAG_WORK_REQUEST){
          
            printf("P%d: Neprisel pesek, ale zadost o praci. Odpovidam prazdnou zpravou.\n", my_rank);        
          
            //nemam praci
            
            MPI_Recv(&token, 1, MPI_INT, MPI_ANY_SOURCE, TAG_WORK_REQUEST, MPI_COMM_WORLD, &status);
            
            int* msg;
            msg = createWorkMessage(1, 0, 1);
            MPI_Send(msg, maxLen, MPI_INT, status.MPI_SOURCE, TAG_SENDING_WORK, MPI_COMM_WORLD);
              
            free(msg);
              
          }else if(status.MPI_TAG == TAG_SENDING_TOKEN){
          
            printf("P%d: Pesek, prijem.\n", my_rank);
          
            MPI_Recv(&token, 1, MPI_INT, MPI_ANY_SOURCE, TAG_SENDING_TOKEN, MPI_COMM_WORLD, &status);
            
            if(my_color == BLACK){
              token = BLACK;
              my_color = WHITE;
            }
              
            printf("P%d: Posilam peska s barvou: %d\n", my_rank, token);
              
            //posle peska dalsimu procesu
      	    MPI_Send(&token, 1, MPI_INT, (my_rank+1)%p, TAG_SENDING_TOKEN, MPI_COMM_WORLD);       
            
          }else if(status.MPI_TAG == TAG_COLLECTING_RESULT){
          
			printf("P%d: Zprava o sberu reseni.\n", my_rank);
          
			//sber zneni nejlepsiho reseni
        	int i;  		
        	   
        	MPI_Recv(resultMessage, trivialUpperBound + 1, MPI_INT, my_rank-1, TAG_COLLECTING_RESULT, MPI_COMM_WORLD, &status);
        
        	if(resultMessage[0] > privateUpperBound){
          		//vytvoreni zpravy
        		resultMessage[0] = privateUpperBound;
        		for(i=1; i<=privateUpperBound; i++){
        			resultMessage[i] = result[i-1];
        		}  		
        		  
        	}
        
            printf("P%d: Preposilam reseni delky: %d\n", my_rank, resultMessage[0]);
            printArray(&(resultMessage[1]), resultMessage[0]);
        
        	  MPI_Send(resultMessage, trivialUpperBound + 1, MPI_INT, (my_rank+1)%p, TAG_COLLECTING_RESULT, MPI_COMM_WORLD);
        
            break;
          }else{
            printf("P%d: Prijem nepodstatne zpravy.\n", my_rank);
            int mess[maxLen];
            MPI_Recv(mess, maxLen, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
          }
        }
     }
  

  }else{
	  /* RANK == 0 - hlavni proces*/

	  /*spocita praci*/
	  totalWork = workload(0, -1);
	  avgWork = totalWork / p;

	  printStats();

		
	  /*inicialni rozdeleni prace*/
	  splitWork(0,-1);

	  MPI_Barrier (MPI_COMM_WORLD);

	  t1 = MPI_Wtime();

	  solve();

  
  
    int token = WHITE;
    my_color = WHITE;

          //posle peska dalsimu procesu
    printf("P%d: Posilam peska.\n", my_rank);
      
    MPI_Send(&token, 1, MPI_INT, 1, TAG_SENDING_TOKEN, MPI_COMM_WORLD);

   int flag = 0;
  
   while(1){
      MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);            
    
      if(status.MPI_TAG == TAG_WORK_REQUEST){
          
		 printf("P%d: Prijmam zadost o praci.\n", my_rank);

          MPI_Recv(&token, 1, MPI_INT, MPI_ANY_SOURCE, TAG_WORK_REQUEST, MPI_COMM_WORLD, &status);
          
          //nemam praci
          int* msg;
          msg = createWorkMessage(1, 0, 1);
          MPI_Send(msg, maxLen, MPI_INT, status.MPI_SOURCE, TAG_SENDING_WORK, MPI_COMM_WORLD);
          free(msg);
            
        }else if(status.MPI_TAG == TAG_SENDING_TOKEN){  
                
			printf("P%d: Prijmam peska.\n", my_rank);

            MPI_Recv(&token, 1, MPI_INT, p-1, TAG_SENDING_TOKEN, MPI_COMM_WORLD, &status);
            
            printf("P%d: Vratil se pesek s barvou %d.\n", my_rank, token);

            
            if(token == BLACK){
              token = WHITE;
    		      MPI_Send(&token, 1, MPI_INT, 1, TAG_SENDING_TOKEN, MPI_COMM_WORLD);
              continue;  
            }else{
              
               /*sber zneni nejlepsiho reseni
          		 - v logickem kruhu poslu zpravu, kam napisu moje nejlepsi reseni;
          		 - prijemce se koukne na velikost reseni a kdyz je autorem lepsiho, tak ho tam prepise
          		*/
          	
          
            	//vytvoreni zpravy
              int i;
              
          	  resultMessage[0] = privateUpperBound;
          	  for(i=1; i<=privateUpperBound; i++){
          		  resultMessage[i] = result[i-1];
          	  }
          
              printf("P%d: Posilam reseni delky: %d\n", my_rank, resultMessage[0]);
              printArray(&(resultMessage[1]), resultMessage[0]);
              
          	  MPI_Send(resultMessage, trivialUpperBound + 1, MPI_INT, 1, TAG_COLLECTING_RESULT, MPI_COMM_WORLD);
          
			  printf("P%d: Prijmam optimalni reseni.\n", my_rank);
          	  //po dokonceni kruhu mi prijde zneni nejlepsiho reseni
          	  MPI_Recv(resultMessage, trivialUpperBound + 1, MPI_INT, p-1, TAG_COLLECTING_RESULT, MPI_COMM_WORLD, &status);
    
              break;
              
            }
         
        
        }else{
          printf("P%d: Prijem nepodstatne zpravy.\n", my_rank);
          int mess[maxLen];
          MPI_Recv(mess, maxLen, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
        }
        
    }


	  //bariera neni potreba - protoze P0 jako posledni dostava zpravu od p-1 s optimalnim resenim

	  //MPI_Barrier (MPI_COMM_WORLD);

	  t2 = MPI_Wtime();


	  printf("P%d: vsichni skoncili, nejlepsi reseni je velikosti %d:\n", my_rank, resultMessage[0]);
	  printArray(&(resultMessage[1]), resultMessage[0]);


	  printf ("\nSpotrebovany cas je %f.\n", t2-t1);

  }



  #ifdef DEBUG
	  if(my_rank == 0){
		  printf("P%d: Nactena matice sousednosti %d x %d:", my_rank, n, n);  
		  printMatrix();  
		  printf("Pocet hran v grafu je: %d\n", e);
		  printf("Stupne uzlu jsou:");
		  printArray(degree, n);
		  printf("Uzly podle stupne:");
		  printArray(vertexes, n);
		  printf("Trivialni dolni mez je: %d\n", lowerBound);
	  }
  #endif

  
  /* shut down MPI */
  MPI_Finalize();

  cleanup();

  return 0;
}



/*********************************

funkce hledajici reseni uzloveho pokryti

*********************************/
void solve(){

	int i, depth, position, temp;
	int* arr;
	int workReq [1];

	int counter = 0;

	int foundSolution = 0;


	while(1){

		//vyber uzel ze zasobniku
		arr = pop();


		if(arr == NULL){
			//zasobnik je prazdny

			
				printf("\nP%d: Doprohledal jsem prideleny podstrom.\n", my_rank);

				//Musi fungovat i pro jedniny procesor - ten o praci nezada nikoho
				if(p == 1){
					//dosla prace - konec
					break;
				}

        //zazadej o praci
        int newWork = getWork();
        
        if(newWork == 0){
          //zadny z darcu nema praci
          return;
        }else{
          //dostal jsem novou praci
          continue;
        }

    } else {
			//zasobnik je neprazdny - prace je

			counter++;

			depth = arr[1];
			solution[depth-1] = arr[0];
			solution_size = depth;

			#ifdef DEBUG
			printf("P%d: Zkousim kombinaci a upperBound je %d: ", my_rank, upperBound);		
			printArray(solution, solution_size);
			#endif


			if((depth >= lowerBound) && (depth < upperBound) && (isSolution() == 1)){


				foundSolution = 1;

				if(depth==lowerBound){
					printf("P%d: Reseni: ", my_rank);
					printArray(solution, solution_size);
					printf("P%d: Nalezeno optimalni reseni, koncim\n", my_rank);

					upperBound = depth;
					privateUpperBound = upperBound;

					//uloz reseni
					for(i=0; i<depth; i++){
						temp = solution[i];
						result[i] = temp;
					}


					/*poslu zpravu vsem ostatnim, aby skoncili*/
					MPI_Request request;			

					char* message = "konec "+my_rank;

					int i;
					for(i=0; i<p; i++){
						if(i == my_rank){
							continue;
						}
						MPI_Isend(message, strlen(message)+1, MPI_CHAR, i, TAG_OPTIMUM, MPI_COMM_WORLD, &request);
					}		

					return;
				}else{
					//jine reseni    			
					if(depth < upperBound && depth <= trivialUpperBound){
						//lepsi nez dosud nejlepsi - aktualizuj horni mez
						upperBound = depth;
						privateUpperBound = upperBound;

						#ifdef DEBUG
						printf("P%d: Reseni: ", my_rank);
						printArray(solution, solution_size);
						printf("P%d: Reseni je aktualne nejlepsi a ma pocet uzlu %d\n", my_rank, depth);
						#endif  				

						//uloz reseni
						for(i=0; i<depth; i++){
							temp = solution[i];
							result[i] = temp;
						}


						/*poslu zpravu vsem ostatnim, aby si upperBound aktualizovali*/
						MPI_Request request;			

						int i;
						for(i=0; i<p; i++){
							if(i == my_rank){
								continue;
							}
							MPI_Isend(&upperBound, 1, MPI_INT, i, TAG_NEW_UPPER_BOUND, MPI_COMM_WORLD, &request);
						}				


					}else{
						#ifdef DEBUG
						printf("P%d: Reseni: ", my_rank);
						printArray(solution, solution_size);
						printf("P%d: Reseni je horsi, nez predchozi nalezene\n", my_rank);
						#endif
					}
				}

			}else if(depth+1 >= upperBound){
				//maximalni hloubka dosazena - neexpanduj dal
				continue;
			}else{

				//expand	
				position = vertex_position[arr[0]];
				for(i = n-1; i > position; i--){
					push(vertexes[i], depth + 1);
				}

			}

		}


		/* jednou za CHECK_MSG_AMOUNT iteraci (expanzi) zkontroluj pomoci Iprobe, zda neprisly nejake informace od ostatnich uzlu*/
		if(counter % CHECK_MSG_AMOUNT == 0){

			int flag = 0;
			MPI_Status status;

			MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);

			while (flag){
				//prisla zprava

				if(status.MPI_TAG == TAG_OPTIMUM){

					//prisla zprava o nalezeni optimalniho reseni => koncim vypocet			

					char message[10];

					printf("P%d: Prisla zprava o nalezeni optimalniho reseni => koncim vypocet\n", my_rank);

					MPI_Recv(message, 10, MPI_CHAR, MPI_ANY_SOURCE, TAG_OPTIMUM, MPI_COMM_WORLD, &status);

					return;

				} else if(status.MPI_TAG == TAG_NEW_UPPER_BOUND){

					//ostatni procesy dostanou zpravu jen o nove upperBound

					int newUpperBound;
					
					printf("P%d: Prisla zprava o novem lepsim reseni delky %d.\n", my_rank, upperBound);

					MPI_Recv(&newUpperBound, 1, MPI_INT, MPI_ANY_SOURCE, TAG_NEW_UPPER_BOUND, MPI_COMM_WORLD, &status);

					if(upperBound >= newUpperBound){
						upperBound = newUpperBound;
					}
					

				} else if (status.MPI_TAG == TAG_WORK_REQUEST){

					//prisla zadost o praci
					printf("P%d: Prisla zadost o praci.\n", my_rank);

					MPI_Recv(workReq, 1, MPI_INT, MPI_ANY_SOURCE, TAG_WORK_REQUEST, MPI_COMM_WORLD, &status);

					// zadost o praci, prijmout a dopovedet
					// zaslat rozdeleny zasobnik a nebo prazdnou praci

					int* msg = splitStack(); 

					//#ifdef DEBUG
					if(msg[0]==1 && msg[1]==0){
						printf("P%d: Posilam procesoru %d zpravu bez prace\n", my_rank, status.MPI_SOURCE);
					} else {
						printf("P%d: Posilam praci procesoru %d\n", my_rank, status.MPI_SOURCE);
					}
					//#endif

					MPI_Send(msg, maxLen, MPI_INT, status.MPI_SOURCE, TAG_SENDING_WORK, MPI_COMM_WORLD);

					//obarvi peska
					my_color = BLACK;

					//uvolni zpravu
					free(msg);
					msg = NULL;

					
				}else {

					//neznama zprava
					printf("P%d: Prisla neznama zprava.\n", my_rank);

				}

				//skus jestli neprislo vice zprav nez jedna
				MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);

			}

		}

	}
}



/*********************************

funkce zada ostatni o praci (maximalne MAX_WORK_REQUESTS krat posle zadost)

*********************************/
int getWork(){
        int numberRequests = 0;
        int hasWork;
        int workReq [1];
        
				//posli request
				#ifdef DEBUG
				  printf("P%d: Posilam zadost o praci procesu %d.\n", my_rank, workDonor);
				#endif

				MPI_Send(workReq, 1, MPI_INT, workDonor, TAG_WORK_REQUEST, MPI_COMM_WORLD);

				numberRequests = 1;
				
				
				while(numberRequests < MAX_WORK_REQUESTS && numberRequests < p-1){

					//prijem prace
					int msg2[maxLen];

					printf("P%d: Prijmam zpravu s praci.\n", my_rank);

					MPI_Recv(msg2, maxLen, MPI_INT, MPI_ANY_SOURCE, TAG_SENDING_WORK, MPI_COMM_WORLD, &status);
		
					// prisel rozdeleny zasobnik, prijmout
					// deserializovat a spustit vypocet - pokud je prace neprazdna
					int hasWork = loadWorkMessage(msg2);

					if(hasWork){
						//#ifdef DEBUG
						printf("P%d: Dostal jsem praci od procesoru %d\n", my_rank, status.MPI_SOURCE);
						//#endif																	

            //uz znovu muze pracovat
						return 1;

					}else{
						
						//procesor workDonor nema praci
						//skus nekoho jineho pokud muzes						

						//#ifdef DEBUG
						  printf("P%d: Procesor %d uz nema praci\n", my_rank, status.MPI_SOURCE);
						//#endif
							
							//vygeneruj dalsiho darce v cyklu krome me
							while((workDonor = (workDonor + 1) % p) == my_rank){}

							//zazadej znovu o praci od nekoho jineho			
							//#ifdef DEBUG
							 printf("P%d: Posilam zadost o praci procesu %d.\n", my_rank, workDonor);
							//#endif

							MPI_Send(workReq, 1, MPI_INT, workDonor, TAG_WORK_REQUEST, MPI_COMM_WORLD);

							numberRequests++;


					}					

				}
				
				printf("P%d: Zadny kandidat nema praci.\n", my_rank);
				return 0;
				
				
}





/*********************************

funkce overi, zda se jedna o pripustne reseni

*********************************/
int isSolution(){

	int i, j;

	for(i=0; i<n; i++){
		for(j=i; j<n; j++){
			if(matrix[i][j]==1){
				if(isInSolution(i, j) == 0){
					return 0;
				}
			}
		}
	}

	return 1;	
}


/*********************************

funkce overi, zda je hrana (i,j) pokryta

*********************************/
int isInSolution(int i, int j){
	int a;
	for(a=0; a<solution_size; a++){
		if(solution[a]==i || solution[a]==j){
			return 1;
		}
	}
	return 0;
}



/*********************************

funkce uvolni zaalokovanou pamet

*********************************/
void cleanup(){
  int i;

  for(i=0; i<n; i++){
	  free(matrix[i]);
  }

  free(matrix);

  free(vertexes);
  free(vertex_position);
  free(degree);

  for(i=0; i<stack_size; i++){
	  free(stack[i]);
  }
  free(stack);

  free(solution);
  free(result);
}

/*********************************

funkce spocte sousedy ke kazdemu uzlu a seradi je do pole vertexes

*********************************/
void sortVertexesByDegree(){
  int i, j, x = 0, sum = 0, min = 1000, max = -1000;

  for(i=0; i<n; i++){
	  if(degree[i]>max){
		  max = degree[i];
		  if(degree[i]<min){
			min = degree[i];
		  }
	  }else if(degree[i]<min){
		  min = degree[i];
	  }
  }

  if(( vertexes = (int*) malloc(n * sizeof(int))) == NULL){
	  fputs("Chyba alokace pole vertexes\n", stderr);
	  exit(-1);
  }

  if(( vertex_position = (int*) malloc(n * sizeof(int))) == NULL){
	  fputs("Chyba alokace pole vertex_position\n", stderr);
	  exit(-1);
  }
  
  for(i=max; i>=min; i--){
	
  	for(j=0; j<n; j++){
  	  if(i==degree[j]){
  	    vertex_position[j] = x;
    		vertexes[x++] = j;
    		if(sum < e){
    			sum += i;
    			lowerBound++;			
    		}
  	  }
  	}
  }
  
}


/*********************************

funkce spocte stupne uzlu

*********************************/
void countDegree(){
  
  int i, j;
  
  if(( degree = (int*) malloc(n * sizeof(int))) == NULL){
	  fputs("Chyba alokace pole degree\n", stderr);
	  exit(-1);
  }
  
  for(i=0; i<n; i++){
    degree[i] = 0;
    for(j=0; j<n; j++){
      degree[i] += matrix[i][j];
    }
  }
   
}


/*********************************

funkce spocte pocet hran grafu

*********************************/
int countEdges(){
  int i, j, sum;
  
  sum = 0;
  
  for(i=0; i<n; i++){
    for(j=0; j<n; j++){
      sum += matrix[i][j];
    }
  }

  return sum / 2;
}




/*********************************

funkce nacte matici ze zadaneho souboru

*********************************/

void loadMatrix(char* filename){

  FILE* matrixFile;
  char number;
  
  int i, j;
  
  matrixFile = fopen(filename, "r");
  
  if(!matrixFile){
    fputs("Nepodarilo se otevrit vstupni soubor.\n", stderr);
    exit(-1);
  }

  n = readNumberOfNodes(matrixFile);  
  
  if(( matrix = (int**) malloc(n * sizeof(int*))) == NULL){
	  fputs("Chyba alokace matrix\n", stderr);
	  exit(-1);
   }

 
  for(i=0; i<n; i++){

     if(( matrix[i] = (int*) malloc(n * sizeof(int))) == NULL){
  	  fputs("Chyba alokace\n", stderr);
  	  exit(-1);
     }

    for(j=0; j<n; j++){
         
      number = fgetc(matrixFile);             

      if((number == EOF) || (number == '\n')){
          if((number == EOF) && ((i<n-1)||(j<n-1))){
            matrix[i][j] = atoi(&number);
  	        printf("konec souboru - soubor neobsahuje dostatek hodnot pro naplneni definovane matice %d x %d\n", n, n);
	          exit(-1);
	        }
          
          if(number == '\n'){
            if(j<n-1){
              printf("radek %d v souboru s matici neobsahuje dostatek hodnot j=%d n-1=%d\n", i+1, j, n-1);
	            exit(-1);
            }
          }

	   }else{            	        
            matrix[i][j] = atoi(&number);
            
            if((number != '0') && (number != '1')){
              fputs("matice sousednosti pouziva jina cisla nez jednicky a nuly!!\n", stderr);
  		        exit(-1);
            }
            
			number = fgetc(matrixFile);
			if(number != ' '){
              fputs("v matici neni za cislem mezera!!\n", stderr);
  		        exit(-1);
            }

	      }
		
     }
     
     number = fgetc(matrixFile);
     if(number != '\n' && number != EOF){
          printf("radek %d matice je prilis dlouhy!!\n", j);
    		  exit(-1);
     }
     
   }
   

  fclose(matrixFile);
}




/*********************************

funkce nacte pocet uzlu grafu

*********************************/
int readNumberOfNodes(FILE* matrixFile){
  
  char* number;
  char* p;
  int countChar;
  int numNodes;
  
     
  if(( number = (char*) malloc(sizeof(char))) == NULL){
	     fputs("Chyba alokace cislo\n", stderr);
	     exit(-1);
  }
  
  countChar = 0;
     
  while(1){
          number = (char*) realloc(number, (countChar+1) * sizeof(char));
	          
          if(number == NULL){
            fputs("Chyba realokace cislo\n", stderr);
            exit(-1);
          }
          
        p = number;
        p += countChar;
        *p = fgetc(matrixFile);
                    

      if((p == number) && ((*p == ' ') || (*p == '\n'))){
	     fputs("ERROR nacitani - soubor obsahuje vice oddelovacu za sebou nebo radek zacina mezerou!\n", stderr);
	     exit(-1);
    	}

      if((*p == ' ') || (*p == EOF) || (*p == '\n')){
          if(*p == EOF){
            *p = 0;
  	        printf("konec souboru - soubor neobsahuje dostatek hodnot pro naplneni definovane matice\n");
	          exit(-1);
	        }          
          
	        *p = 0;
	        	        
          numNodes = atoi(number);
          
          countChar = 0;
          free(number);
          
          break;
      }else{
		      if(((*p <'0') || (*p >'9')) && (*p != '\n')){
	  	      fputs("soubor matice obsahuje pravdepodobne jine znaky nez cisla!!\n", stderr);
		        exit(-1);
		      }
	    }		
      countChar++;
     }
     return numNodes;
}



/*********************************

funkce vytiskne matici sousednosti na vystup

*********************************/
void printMatrix(){
	printMatrix2(matrix, n, n);
}

/*********************************

funkce vytiskne matici o rozmerech x,y na vystup

*********************************/
void printMatrix2(int** arr, int x, int y){
  int i, j;

  printf("\n");
  
  for(i=0; i<x; i++){
   for(j=0; j<y; j++){
    printf("%d ", arr[i][j]);
   }
  printf("\n");
  } 
}

/*********************************

funkce vytiskne pole na vystup

*********************************/
void printArray(int* arr, int x){

  int i;

  for(i=0; i<x; i++){
    printf("%d ", arr[i]);
   }
  printf("\n");
   
}


/*********************************

funkce vytiskne pole na vystup

*********************************/
void countStats(){


	  e = countEdges();	  
	  
	  countDegree();
	  

	  trivialUpperBound = n-1 < e/2+e%2 ? n-1 : e/2+e%2;
	  upperBound = trivialUpperBound + 1;
	  privateUpperBound = upperBound;
	  
	  sortVertexesByDegree();

}




/*********************************

funkce vytiskne statistiky nacteneho grafu na vystup

*********************************/
void printStats(){

	  printf("Nactena matice sousednosti %d x %d:", n, n);  
	  printMatrix();
	  
	  printf("Pocet hran v grafu je: %d\n",  e);

	  printf("Stupne uzlu jsou: ");
	  printArray(degree, n);
	  	  
	  printf("Trivialni horni mez je: %d\n", trivialUpperBound);

	  printf("Uzly podle stupne: ");
	  printArray(vertexes, n);
	  printf("Pozice uzlu v poli vertexes: ");
	  printArray(vertex_position, n);
	  printf("Trivialni dolni mez je: %d\n", lowerBound);

	  printf("Celkova prace: %ld\n",  totalWork);
	  printf("Prumerna prace: %ld\n",  avgWork);

}


/*********************************

funkce alokuje zasobnik potrebne velikosti

*********************************/
void initializeStack(){

  int i;
  stack_size = 1;
  stack_pointer = -1;

  stack_size = n * upperBound;

  if(( stack = (int**) malloc(stack_size * sizeof(int*))) == NULL){
	fputs("Chyba alokace zasobniku\n", stderr);
	exit(-1);
  }

  for(i=0; i<stack_size; i++){
    if(( stack[i] = (int*) malloc(2 * sizeof(int))) == NULL){
  		fputs("Chyba alokace zasobniku\n", stderr);
  		exit(-1);
  	}
  }

}


/*********************************

funkce na inicializaci poli reseni

*********************************/  
void initializeSolutionArrays(){
  solution_size = -1;

  if(( solution = (int*) malloc(upperBound * sizeof(int))) == NULL){
	fputs("Chyba alokace solution\n", stderr);
	exit(-1);
  }

  if(( result = (int*) malloc(upperBound * sizeof(int))) == NULL){
	fputs("Chyba alokace result\n", stderr);
	exit(-1);
  }
}

/*********************************

funkce vybere polozku ze zasobniku

*********************************/
int* pop(){
  return stack_pointer==-1?NULL:stack[stack_pointer--];
}

/*********************************

funkce vlozi polozku na zasobnik

*********************************/
int push(int i, int depth){
	if(stack_pointer==stack_size){
		return 0;
	}
	stack_pointer++;
	stack[stack_pointer][0] = i;
	stack[stack_pointer][1] = depth;
	return 1;
}

/*********************************

funkce spocita praci potrebnou k expanzi

spocita praci uzlu se stanovenym indexem z pole vertexes ve stanovene hloubce 
az po upperBound - toto cislo urcuje kolik uzlu je treba projit pri vypoctu

*********************************/
long workload(int depth, int index){
	
	long work;
	if (depth < upperBound) {

        //prace az do konce stromu
        work = (1 << (n - index - 1));

        //je treba odecist praci pod upperBound
        int i = index + (upperBound - depth);
        if (i < n) {
			work -= (1 << (n - i - 1)) - 1;
        }
        return work;
    }
    //pouze sam sebe poklada za praci
    return 1;
}

/*********************************

rekurzivni funkce rozdeli praci po jednotlivych urovnich

Pozn: prace se nemusi vzdy dostat na vsechny!!!
avsak neni vytvoreno vice prace nez je mozne

*********************************/
void splitWork(int depth, int index) {
	long work, sumWork = 0;

	if (depth > 0) {
		solution[depth - 1] = vertexes[index];
		solution_size = depth;
		if(solution_size >= lowerBound){
			//muze byt reseni
			if(isSolution()){
				//je reseni
				//je treba ukoncit rozesilani zprav a poslat zpravu o optimu
				//temer nulova pravdepod. - slozity handling a proto vynechano
				printf("P%d: Nasel optimalni reseni pri uvodnim prerozdelovani prace: ", my_rank);
				printArray(solution, solution_size);
			}
		}
	}else{
		p_alloc = 0;
	}

	int i, firstIndex = n - 1, lastIndex = n - 1, process = p_alloc;

	p_alloc++;

	for (i = index + 1; i < n; i++) {

		work = workload(depth + 1, i);

		//hodi se
		if (sumWork + work < avgWork) {
			//vejde se

			lastIndex = i;
			if (sumWork == 0) {
				firstIndex = i;
			}
			sumWork += work;

		} else {
			//nevejde se

			if (p_alloc <= p - 1) {
				//lze expandovat
				if (sumWork > 0) {
					//je co posilat - lastIndex a firstIndex je treba prohodit
					sendWork(process, depth + 1, lastIndex, firstIndex);                       
					sumWork = 0;
					process = p_alloc;
					p_alloc++;
					//skus to znovu
					i--;
				} else {
					//jednina prace a presto je velka
					//rozdel ji pokud muzes
					splitWork(depth + 1, i);
				}
			} else {
				//nelze expandovat
				//vloz praci - i kdyz je ji hodne
				lastIndex = i;
				if (sumWork == 0) {
					firstIndex = i;
				}
				sumWork += work;
			}

		}
	}

	if (sumWork > 0) {
		//nektera prace zbyla - lastIndex a firstIndex je treba prohodit
		sendWork(process, depth + 1, lastIndex, firstIndex);
	}
}

/*********************************

Posle zpravu s inicialni praci

*********************************/
void sendWork(int proc, int depth, int firstIndex, int lastIndex){

	int* msg;

	if(proc == 0){
		//lokalni prace
		int j;
		solution_size = depth;
		
		#ifdef DEBUG
			printf("P0: Castecne reseni: ");
			printArray(solution, depth-1);
		#endif

		for(j = lastIndex; j <= firstIndex; j++){
			push(vertexes[j], depth);

			#ifdef DEBUG
				printf("P0: Lokalni prace procesoru %d\n", vertexes[j]);
			#endif
		} 

	}else{
		//vytvoreni a poslani zpravy s praci
		msg = createWorkMessage(depth, firstIndex, lastIndex);
		
		#ifdef DEBUG
			printf("P0: Posilam inicialni praci procesoru %d\n", proc);
		#endif

		MPI_Send(msg, maxLen, MPI_INT, proc, TAG_SENDING_WORK, MPI_COMM_WORLD);

		//uvolni zpravu
		free(msg);
		msg = NULL;
	}
}


/*********************************

Vytvori zpravu s praci zakodovanou v poli int

Funkce ocekava firstIndex vetsi nebo roven lastIndex

Prazdna zprava:
	createWorkMessage(1, 0, 1);

*********************************/
int* createWorkMessage(int depth, int firstIndex, int lastIndex){

	int * msg;
	int len = depth + 2 + firstIndex - lastIndex, i;
	if(( msg = (int*) malloc(len * sizeof(int))) == NULL){
		fputs("Chyba alokace msg\n", stderr);
		exit(-1);
	}
	msg[0] = depth;
	for(i = 1; i <= depth-1; i++){
		msg[i] = solution[i-1];
	}
	msg[depth] = firstIndex - lastIndex + 1;
	int k = 0;
	for(i = depth + 1; i < len; i++){
		msg[i] = vertexes[lastIndex+k];
		k++;

		#ifdef DEBUG
			printf("P%d: Pracovni uzel k zaslani: %d\n", my_rank, msg[i]);
		#endif
	}

/*
	#ifdef DEBUG
		printf("P0: Zprava: ");
		printArray(msg, len);

		printf("P%d: Castecne reseni: ", my_rank);
		printArray(solution, depth-1);
	#endif
*/

	return msg;
}


/*********************************

Nacte prijatou zpravu s praci

Mozne stavy:
	1 - prace v poradku nactena
	0 - neni prace

*********************************/
int loadWorkMessage(int* msg){
	int depth = msg[0], i;
	for(i = 1; i <= depth-1; i++){
		solution[i-1] = msg[i];
	}
	solution_size = depth - 1;
	int cnt = msg[depth];
	if(cnt == 0){
		//neni prace
		#ifdef DEBUG
			printf("P%d: Neni prace", my_rank);
		#endif
		return 0;
	}
	
	#ifdef DEBUG
		printf("P%d: Castecne reseni: ", my_rank);
		printArray(solution, depth-1);
	#endif
	
	for(i = 1; i <= cnt; i++){
		push(msg[depth + i], depth);

		#ifdef DEBUG
			printf("P%d: Pracovni uzel: %d\n", my_rank, msg[depth+i]);
		#endif
	}

	return 1;
}


/*********************************

Vytvori zpravu s praci tak, ze posle vybere cast prace ze zasobniku

*********************************/
int* splitStack(){
	
	int* arr;
	int* msg;
	int i;

	long stackWork [stack_pointer+1];

	long sumWork = 0;

	//spocita praci v zasobniku
	for(i = 0; i <= stack_pointer; i++){

		arr = stack[i];

		stackWork[i] = workload(arr[1], arr[0]);

		sumWork += stackWork[i];

	}

	if(sumWork < MIN_WORK_SIZE){
		//prilis malo prace
		//vrat prazdnou praci

		#ifdef DEBUG
			printf("P%d: Nemam praci k poslani. ", my_rank);
		#endif

		return createWorkMessage(1, 0, 1);
	}

	//vyber priblizne polovinu prace
	long sendWork = 0, halfWork = sumWork/2;
	int depth = stack[0][1];
	int firstIndex, lastIndex, last;

	//vybira praci ze zasobniku
	for(i = 0; i <= stack_pointer; i++){

		arr = stack[i];

		if(sendWork + stackWork[i] <= halfWork && arr[1] == depth){
			//pokud se vejde a zaroven je ve stejne hloubce

			last = i;
			lastIndex = vertex_position[arr[0]];
			if(sendWork == 0){
				firstIndex = vertex_position[arr[0]];
			}

			sendWork += stackWork[i];

		} else {
			//nevejde se
			if(sendWork == 0){
				//uz prvni uzel se nevejde - vyber ho
				lastIndex = vertex_position[arr[0]];
				firstIndex = vertex_position[arr[0]];
				last = i;
			}

			//vytvor zpravu s praci
			if(firstIndex < lastIndex){
				//first index musi byt >= last index
				i = lastIndex;
				lastIndex = firstIndex;
				firstIndex = i;
			}
			//vytvor zpravu s praci
			msg = createWorkMessage(depth, firstIndex, lastIndex);

			break;
		}
	}

	//posun zbytek zasobniku o tolik polozek kolik si vybral
	last++;
	
	for(i = last; i <= stack_pointer; i++){
		stack[i-last][0] = stack[i][0];
		stack[i-last][1] = stack[i][1];
	}
	//jeste posun stack_pointer
	stack_pointer -= last;

	#ifdef DEBUG
		printf("P%d: Prace je pridelena. ", my_rank);
	#endif

	return msg;
}

